package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ListNode;
import com.cuz.daileetcode.utils.ListNodeUtils;
import java.util.Objects;

public class Day29 {


    /****
     * 给点两个有环或者无环的单链表
     * 如果两个链表相交返回第一个共有节点或者返回null
     * @param head1 链表1
     * @param head2 链表2
     * @return 共有节点
     */
    public static ListNode intersectionNodeBetween(ListNode head1, ListNode head2) {
        //任何一个头节点为null 那么必不可能相交
        if (head1 == null || head2 == null) {
            return null;
        }
        ListNode loop1 = findFirstLoopNode(head1);
        ListNode loop2 = findFirstLoopNode(head1);
        //如果都不成环 且尾节点地址一样 那么说明成Y字形 找第一个相同节点
        if (loop1 == null && loop2 == null) {
            //for循环拿到尾巴节点和长度
            ListNodeUtils.TailAndLen tailAndLen1 = ListNodeUtils.getTailAndLen(head1);
            ListNodeUtils.TailAndLen tailAndLen2 = ListNodeUtils.getTailAndLen(head2);
            //如果两个链表尾巴节点不同那么肯定不相交
            if (tailAndLen1.getTail() != tailAndLen2.getTail()) {
                return null;
            }
            int len1 = tailAndLen1.getLen();
            int len2 = tailAndLen1.getLen();
            return intersectionNodeBetweenNoLoop(head1, head2, tailAndLen1.getTail(), len1, len2);
        }
        //不存在 一个链表成环 一个链表不成环还相交 ，因为单链表成环的那么肯定不相交

        //如果成环 且成环节点相同 说明呈 Y字母下面你拼结上6的形状
        if (loop1 == loop2) {
            //忽略环的部分 认为入环节点就是他们的尾巴 让长的先走长度差值步
            //和无环不相交一样
            int d1 = ListNodeUtils.distanceBetween(head1, loop1);
            int d2 = ListNodeUtils.distanceBetween(head2, loop1);
            return intersectionNodeBetweenNoLoop(head1, head2, loop1, d1, d2);
        } else {
            //说明 第一种情况 不相交 成两个6字形 返回null
            //第二种情况 相交 像一个蜗牛 一个O上面两个触角 返回loop1 or loop2(都是第一个公有节点，只是loop1离head1近，loop2离head2近)
            //进入到这个else 只能是这两种情况
            //(其实还可能是一个成环，一个不成环 那么二者一定不相交 情况3)

            //处理情况3
            if (loop1 == null || loop2 == null) {
                return null;
            }
            //如何区分情况1和情况2 ，让 loop继续往下走 在回到起点之前碰到loop2 那么说明为情况2，反之为1
            ListNode temp = loop1;
            while (temp != loop2) {
                temp = temp.next;
                if (temp == loop1) {
                    return null;
                }
            }
            return loop1;
        }
    }

    /***
     * 找两个无环相交链表的第一个共有节点
     *
     * 二者形成Y形状
     * 让长度更长的链表先走 Math.abs(len1 - len2) 步
     * 然后一起触发 一定会在第一个共有节点处相交
     * @param head1 头节点1
     * @param head2 头节点2
     * @param len1 头节点1链表长度
     * @param len2 头节点1链表长度
     * @return ListNode 第一个共有节点
     */
    private static ListNode intersectionNodeBetweenNoLoop(ListNode head1, ListNode head2, ListNode end, int len1, int len2) {
        Objects.requireNonNull(head1);
        Objects.requireNonNull(head2);
        Objects.requireNonNull(end);
        ListNode goFirst;
        ListNode goLast;
        if (len1 > len2) {
            goFirst = head1;
            goLast = head2;
        } else {
            goFirst = head2;
            goLast = head1;
        }
        for (int step = 0; step < Math.abs(len1 - len2); step++) {
            goFirst = goFirst.next;
        }
        //不同 且没到end处
        while (goFirst != goLast && goFirst != end) {
            goFirst = goFirst.next;
            goLast = goLast.next;
        }
        return goFirst;
    }


    /***
     * 找成环链表中的入环节点
     *
     * @param head
     * @return
     */
    public static ListNode findFirstLoopNode(ListNode head) {
        //单链表如果节点数小2 不可能相交
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        boolean isHasLoop = false;
        while (fast != null || fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                isHasLoop = true;
                break;
            }
        }
        if (!isHasLoop) {
            return null;
        } else {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
}
